#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_OP 100010
#define HASH_SIZE 200003

int min_heap[MAX_OP], min_heap_size = 0;

int max_heap[MAX_OP], max_heap_size = 0;

int hash_key[HASH_SIZE], hash_val[HASH_SIZE];

void swap(int* a, int* b) 
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void init_hash()
{
    for (int i = 0; i < HASH_SIZE; i++) 
    {
        hash_key[i] = -1;
        hash_val[i] = 0;
    }
}

int get_hash(int x) 
{
    return (x % HASH_SIZE + HASH_SIZE) % HASH_SIZE;
}

void hash_upsert(int x, int delta)
{
    int idx = get_hash(x);
    while (1)
    {
        if (hash_key[idx] == -1) 
        {  
            hash_key[idx] = x;
            hash_val[idx] = delta;
            return;
        }
        if (hash_key[idx] == x) 
        {  
            hash_val[idx] += delta;
            return;
        }
        idx = (idx + 1) % HASH_SIZE; 
    }
}

int hash_find(int x) 
{
    int idx = get_hash(x);
    while (hash_key[idx] != -1) 
    {
        if (hash_key[idx] == x) 
        {
            return hash_val[idx];
        }
        idx = (idx + 1) % HASH_SIZE;
    }
    return 0;  
}

void min_heap_swim(int i) 
{
    while (i > 0) 
    {
        int parent = (i - 1) / 2;
        if (min_heap[parent] > min_heap[i])
        {
            swap(&min_heap[parent], &min_heap[i]);
            i = parent;
        }
        else 
        {
            break;
        }
    }
}

void min_heap_sink(int i)
{
    while (2 * i + 1 < min_heap_size)
    {
        int left = 2 * i + 1;
        int right = left + 1;
        int min_child = left;
        if (right < min_heap_size && min_heap[right] < min_heap[left]) 
        {
            min_child = right;
        }
        if (min_heap[min_child] < min_heap[i])
        {
            swap(&min_heap[i], &min_heap[min_child]);
            i = min_child;
        }
        else 
        {
            break;
        }
    }
}

void min_heap_push(int x) 
{
    min_heap[min_heap_size++] = x;
    min_heap_swim(min_heap_size - 1);
}

void min_heap_pop() 
{
    min_heap[0] = min_heap[--min_heap_size];
    min_heap_sink(0);
}

void clean_min_heap() 
{
    while (min_heap_size > 0) 
    {
        int top = min_heap[0];
        if (hash_find(top) <= 0)
        {
            min_heap_pop();
        }
        else {
            break;
        }
    }
}

void max_heap_swim(int i) 
{
    while (i > 0) 
    {
        int parent = (i - 1) / 2;
        if (max_heap[parent] < max_heap[i]) 
        {
            swap(&max_heap[parent], &max_heap[i]);
            i = parent;
        }
        else 
        {
            break;
        }
    }
}

void max_heap_sink(int i) 
{
    while (2 * i + 1 < max_heap_size)
    {
        int left = 2 * i + 1;
        int right = left + 1;
        int max_child = left;
        if (right < max_heap_size && max_heap[right] > max_heap[left]) 
        {
            max_child = right;
        }
        if (max_heap[max_child] > max_heap[i]) 
        {
            swap(&max_heap[i], &max_heap[max_child]);
            i = max_child;
        }
        else 
        {
            break;
        }
    }
}

void max_heap_push(int x) 
{
    max_heap[max_heap_size++] = x;
    max_heap_swim(max_heap_size - 1);
}

void max_heap_pop() 
{
    max_heap[0] = max_heap[--max_heap_size];
    max_heap_sink(0);
}

void clean_max_heap() 
{
    while (max_heap_size > 0) 
    {
        int top = max_heap[0];
        if (hash_find(top) <= 0) 
        {
            max_heap_pop();
        }
        else
        {
            break;
        }
    }
}

int main()
{
    init_hash();  
    int n;
    scanf_s("%d", &n);  

    for (int i = 0; i < n; i++) 
    {
        int op;
        scanf_s("%d", &op); 

        if (op == 1) 
        {  
            int x;
            scanf_s("%d", &x);
            hash_upsert(x, 1);  
            min_heap_push(x);   
            max_heap_push(x);  
        }
        else if (op == 2) 
        {  
            clean_min_heap();   
            printf("%d\n", min_heap[0]); 
        }
        else if (op == 3) 
        { 
            clean_max_heap();  
            printf("%d\n", max_heap[0]); 
        }
        else if (op == 4) 
        {  
            clean_min_heap();   
            int min_val = min_heap[0];
            hash_upsert(min_val, -1); 
            min_heap_pop();    
        }
        else if (op == 5)
        {  
            clean_max_heap();  
            int max_val = max_heap[0];
            hash_upsert(max_val, -1); 
            max_heap_pop();  
        }
    }

    return 0;
}